package com.example;

/**
 * @Author loubobooo
 * @Description #92. 反转链表 II
 * @Date 2022/3/11
 */
public class ReverseLinkedListIi {

    /**
     * 方法描述:给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。
     * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * 示例 1：
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     *
     * @param:
     * @return:
     * @author: loubobooo
     * @date: 2022/3/11
     */
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode superior = dummyHead;
        // 找到最左节点
        for (int i = 1; i < left; i++) {
            superior = superior.next;
        }
        ListNode prev = null;
        ListNode cur = superior.next;
        for (int i = 0; i <= right - left; i++) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        // 修改m和n-m位置处的节点的指向
        superior.next.next = cur;
        superior.next = prev;
        return dummyHead.next;
    }


}
